package com.easy.carl.algorithm.array.binarySearch;

/**
 * @ClassName SearchInsert35
 * @Description 35. 搜索插入位置
 * @Author zheng
 * @Date 2021/12/9 16:08
 * @Version 1.0
 **/
public class SearchInsert35 {
    public int searchInsert(int[] nums, int target) {
        //左边界
        int left = 0;
        //右边界是nums.length,nums[right]其实是无效位置
        //所以整个区间是左闭右开区间
        int right = nums.length;
        //左闭右开区间
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                //nums[mid]的值大于target，下一次去左区间找
                //因为是左闭右开区间，下一次不会比较right位置上的值
                //所以right更新为mid
                right = mid;
            } else {
                //nums[mid]的值小于target，下一次从右区间找
                //因为下一次比较时包含左边界，所以left的值要更新为mid+1;
                left = mid + 1;
            }
        }
        return right;
    }
}
